package euler.p001_050;

import euler.MainEuler;

public class Euler031 extends MainEuler {

    /*
        In England the currency is made up of pound, £, and pence, p,
        and there are eight coins in general circulation:

            1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

        It is possible to make £2 in the following way:

            1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

        How many different ways can £2 be made using any number of coins?
     */

    public String resolve() {
        int cantidad = 200;
        return String.valueOf(soluciones(200,cantidad));
        // 73682
    }

    private static int soluciones(int valor, int cantidad) {
        if (cantidad <= 0) {
            return 1;
        }
        if (valor == 1) {
            return 1;
        }

        int suma = 0;

        for (int i = 0; i*valor <= cantidad  ; i++) {
            suma+=soluciones(nextValor(valor),cantidad - i*valor);
        }

        return suma;
    }

    private static int nextValor(int valor) {
        switch (valor) {
            case 200: return 100;
            case 100: return 50;
            case 50: return 20;
            case 20: return 10;
            case 10: return 5;
            case 5: return 2;
            case 2: return 1;
            default: throw new IllegalArgumentException("Valor invalido " + valor);
        }
    }

}
